The Salsa quarter-round function. Four parallel copies make a round. |
|
| General | |
|---|---|
| Related to | Rumba20, ChaCha |
| Certification | eSTREAM portfolio |
| Cipher detail | |
| Key sizes | 256 bits |
| State size | 512 bits |
| Rounds | 20 |
| Speed | 4.25 cpb on Intel Woodcrest[1] |
| Best public cryptanalysis | |
| 2008 cryptanalysis breaks 8 out of 20 rounds to recover the 256-bit secret key in 2251 operations, using 231 keystream pairs.[2] | |
Salsa20 is a stream cipher submitted to eSTREAM by Daniel Bernstein. It is built on a pseudorandom function based on 32-bit addition, bitwise addition (XOR) and rotation operations, which maps a 256-bit key, a 64-bit nonce (number used once), and a 64-bit stream position to a 512-bit output (a version with a 128-bit key also exists). This gives Salsa20 the unusual advantage that the user can efficiently seek to any position in the output stream. It offers speeds of around 4–14 cycles per byte in software on modern x86 processors,[3] and reasonable hardware performance. It is not patented, and Bernstein has written several public domain implementations optimized for common architectures.[4]
Contents |
Internally, the cipher uses bitwise addition (exclusive OR), 32-bit addition mod 232, and constant-distance rotation operations on an internal state of 16 32-bit words. This choice of operations avoids the possibility of timing attacks in software implementations.
The initial state is made up of 8 words of key, 2 words of stream position, 2 words of nonce (essentially additional stream position bits), and 4 fixed words. 20 rounds of mixing produce 16 words of stream cipher output.
Each round consists of four quarter-round operations, performed on either the columns or the rows of the 16-word state, arranged as a 4×4 matrix. Every 2 rounds, the pattern repeats. Pseudocode for two rounds is as follows. ⊞ is addition modulo 232, <<< is the left-rotate operation, and ^ is exclusive-or. x ^= y is an abbreviation for x = x ^ y.
x[ 4] ^= (x[ 0] ⊞ x[12])<<<7; x[ 9] ^= (x[ 5] ⊞ x[ 1])<<<7; x[14] ^= (x[10] ⊞ x[ 6])<<<7; x[ 3] ^= (x[15] ⊞ x[11])<<<7; x[ 8] ^= (x[ 4] ⊞ x[ 0])<<<9; x[13] ^= (x[ 9] ⊞ x[ 5])<<<9; x[ 2] ^= (x[14] ⊞ x[10])<<<9; x[ 7] ^= (x[ 3] ⊞ x[15])<<<9; x[12] ^= (x[ 8] ⊞ x[ 4])<<<13; x[ 1] ^= (x[13] ⊞ x[ 9])<<<13; x[ 6] ^= (x[ 2] ⊞ x[14])<<<13; x[11] ^= (x[ 7] ⊞ x[ 3])<<<13; x[ 0] ^= (x[12] ⊞ x[ 8])<<<18; x[ 5] ^= (x[ 1] ⊞ x[13])<<<18; x[10] ^= (x[ 6] ⊞ x[ 2])<<<18; x[15] ^= (x[11] ⊞ x[ 7])<<<18; x[ 1] ^= (x[ 0] ⊞ x[ 3])<<<7; x[ 6] ^= (x[ 5] ⊞ x[ 4])<<<7; x[11] ^= (x[10] ⊞ x[ 9])<<<7; x[12] ^= (x[15] ⊞ x[14])<<<7; x[ 2] ^= (x[ 1] ⊞ x[ 0])<<<9; x[ 7] ^= (x[ 6] ⊞ x[ 5])<<<9; x[ 8] ^= (x[11] ⊞ x[10])<<<9; x[13] ^= (x[12] ⊞ x[15])<<<9; x[ 3] ^= (x[ 2] ⊞ x[ 1])<<<13; x[ 4] ^= (x[ 7] ⊞ x[ 6])<<<13; x[ 9] ^= (x[ 8] ⊞ x[11])<<<13; x[14] ^= (x[13] ⊞ x[12])<<<13; x[ 0] ^= (x[ 3] ⊞ x[ 2])<<<18; x[ 5] ^= (x[ 4] ⊞ x[ 7])<<<18; x[10] ^= (x[ 9] ⊞ x[ 8])<<<18; x[15] ^= (x[14] ⊞ x[13])<<<18;
These operations can be performed very efficiently using the x86 SSE2 instruction set.
Salsa20 performs 20 rounds of mixing on its input. However, reduced round variants Salsa20/8 and Salsa20/12 using 8 and 12 rounds respectively have also been introduced. These variants were introduced to complement the original Salsa20, not to replace it, and perform even better in the eSTREAM benchmarks than the already competitive Salsa20.
Salsa20 has been selected as a Phase 3 design for Profile 1 (software) by the eSTREAM project, receiving the highest weighted voting score of any Profile 1 algorithm at the end of Phase 2.[5] Salsa20 had previously been selected as Phase 2 Focus design for Profile 1 (software) and as a Phase 2 design for Profile 2 (hardware) by the eSTREAM project [6], but was not advanced to Phase 3 for Profile 2 because eSTREAM felt that it was probably not a good candidate for extremely resource constrained hardware environments.[7]
In 2005, Paul Crowley reported an attack on Salsa20/5 with an estimated time complexity of 2165, and won Bernstein's US$1000 prize for "most interesting Salsa20 cryptanalysis".[8] This attack, and all subsequent attacks are based on truncated differential cryptanalysis. In 2006, Fischer, Meier, Berbain, Biasse, and Robshaw reported an attack on Salsa20/6 with estimated time complexity of 2177, and a related-key attack on Salsa20/7 with estimated time complexity of 2217.[9]
In 2007, Tsunoo et al. announced a cryptanalysis of Salsa20 which breaks 8 out of 20 rounds to recover the 256-bit secret key in 2255 operations, using 211.37 keystream pairs.[10]. However, this attack does not seem to be comparative with the brute force attack.
As of 2008[update], Aumasson, Fischer, Khazaei, Meier, and Rechberger[2] reported a cryptanalytic attack against Salsa20/7 with a time complexity of 2153, and they reported the first attack against Salsa20/8 with an estimated time complexity of 2251. This attack makes use of the new concept of probabilistic neutral key bits for probabilistic detection of a truncated differential. The attack can be adapted to break Salsa20/7 with a 128-bit key. There are no published attacks on Salsa20/12 or the full Salsa20/20.
In 2008, Bernstein published the closely related "ChaCha" family of ciphers, which aim to increase the diffusion per round while achieving the same or slightly greater performance.[11] The Aumasson et al. paper also attacks ChaCha, achieving one round less: ChaCha6 with complexity 2140 and ChaCha7 with complexity 2231.[2]
ChaCha replaces the basic Salsa20 round primitive R(a,b,c,k)
b ⊕= (a ⊞ c) <<< k;
with the modified computation:
b ⊞= c; a ⊕= b; a <<<= k;
The rotation amounts are also updated. A full quarter-round becomes:
a ⊞= b; d ⊕= a; d <<<= 16; c ⊞= d; b ⊕= c; b <<<= 12; a ⊞= b; d ⊕= a; d <<<= 8; c ⊞= d; b ⊕= c; b <<<= 7;
In addition to being more efficient on 2-operand instruction sets (like x86), this updates each word twice per quarter-round.
The fact that two of the rotates are multiple of 8 allows some optimization.[12] Additionally, the input formatting is rearranged to support an efficient SSE implementation optimization discovered for Salsa20. Rather than alternating rounds down columns and across rows, they are performed down columns and along diagonals.[13]
ChaCha is the basis of the BLAKE hash function, a finalist in the NIST hash function competition.
|
|||||||||||||||||||||||||||||